#include <stdlib.h>
#include <stdio.h>

namespace QUEUE {
    typedef struct QueueNode {
        char data;
        struct QueueNode *pNext;
    }QUEUENODE, *PQUEUENODE;
    
    typedef struct QUEUE {
        PQUEUENODE front;
        PQUEUENODE rear;
    }QUEUE, *PQUEUE;
    
    PQUEUE create_queue() {
        PQUEUE pQ = (PQUEUE)malloc(sizeof(QUEUENODE));
        pQ->front = (PQUEUENODE)malloc(sizeof(QUEUENODE));
        if(pQ==NULL||pQ->front==NULL) {
            printf("malloc failed\n");
        } else {
            pQ->rear = pQ->front;
            pQ->front->pNext = NULL;
        }
        return pQ;
    }
    
    bool is_queue_empty(PQUEUE pQ) {
        if(pQ->front == pQ->rear) {
            return true;
        } else {
            return false;
        }
    }
    
    void en_queue(PQUEUE pQ, char val) {
        PQUEUENODE pNew = (PQUEUENODE)malloc(sizeof(QUEUENODE));
        if(pNew==NULL) {
            printf("malloc failed\n");
            exit(-1);
        } else {
            pNew->data = val;
            pNew->pNext = NULL;
            pQ->rear->pNext = pNew;
            pQ->rear = pNew;
        }
    }
    
    bool de_queue(PQUEUE pQ, char* pData) {
        if(is_queue_empty(pQ)) {
            return false;
        } else {
            PQUEUENODE p = pQ->front->pNext;
            *pData = p->data;
            pQ->front->pNext=p->pNext;
            if(pQ->rear==p) {
                pQ->rear = pQ->front;
            }
            free(p);
        }
        return true;
    }
    
    void destroy_queue(PQUEUE pQ)
    {
        if(is_queue_empty(pQ))
            return;
        else
        {
            while(pQ->front)
            {
                pQ->rear = pQ->front->pNext;
                free(pQ->front);
                pQ->front = pQ->rear;
            }
        }
        free(pQ);
        pQ = 0;
        return;
    }
    
    void traverse_queue(PQUEUE pQ)
    {
        if(is_queue_empty(pQ))
            printf("there is no data in the queue!\n");
        else
        {
            PQUEUENODE pCurrent = pQ->front->pNext;
            while(pCurrent)
            {
                printf("%c",pCurrent->data);
                pCurrent = pCurrent->pNext;
            }
            printf("\n");
        }
        return;
    }
}
